// 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

// 例如：
// 给定二叉树 [3,9,20,null,null,15,7],


function levelOrderBottom(root: TreeNode): number[][] {
    if (!root) { // 边界检测
        return [];
    }
    const res: number[][] = []; // 结果数组
    const queue: TreeNode[] = [root]; // 队列初始化
    while (queue.length > 0) {
        let currLen = queue.length;
        let currRes = []; // 当前层数数组
        for (let i = 0; i < currLen; i++) {
            let curr = queue.shift()!;
            currRes.push(curr.val);
            if (curr.left) queue.push(curr.left);
            if (curr.right) queue.push(curr.right);
        }
        res.unshift(currRes);// 因为是从下往上输出，所以这里要从头部插入结果数组
    }
    return res;
};



// 这道题目是一道难度比较小的广度优先遍历算法求解的题目
// 说到BFS，比较容易想到的就是用一个队列来显式的模拟这个过程
// 一般来说书写上要注意的有以下几个点：
// 1. 初始化时需要加入根节点入队列
// 2. 为了保证“层序”的结果数组合理，每一轮次输出的节点个数应该根据队列的长度提前记录，
// 否则可能出现当前层数数组出现别的层的节点
// 3. 有子节点的情况下才加入队列
// 此外这道题目额外留意一点，因为是要求从下到上输出，所以当前层数组加入结果数组应该是以一个头部插入的顺序而不是尾部加入。


